This invention relates generally to computer memory management and more particularly to tracing-type garbage collection.
Garbage collection is the process of automatically reclaiming usable memory spaces in a computer memory by locating objects (blocks of memory) that are no longer needed, independently of the programs which request the allocation of such memory spaces. It is not always advisable to permit user programs to de-allocate the space allocated for the objects they create. This is because other programs may contain references to these objects, and premature deallocation would cause an error.
Garbage collectors must verify that there are no references (pointers) to an object, i.e., that the object is inaccessible, before deallocating the object's memory space. There are two general approaches to garbage collection: reference counting and tracing. Reference counting garbage collectors maintain a count of how many references there are to each object. If the reference count is zero, the block of memory can be de-allocated (reclaimed). Reference-counting garbage collectors are efficient to execute but they have several limitations. They fail to recognize inaccessible "cyclic structures", which directly or indirectly reference themselves. Further, the maintenance of reference counts uses up space and can noticeably slow the performance of the user program.
Tracing garbage collectors periodically trace pointers, starting with a root set of objects. All objects pointed to by the root set are identified as reachable. Reachable objects are either marked or copied to another location. All objects pointed to by reachable objects are also identified as reachable. The process continues until all memory objects reachable from the root set have been found. What remains as unmarked (or uncopied) is inaccessible, and thus garbage. These inaccessible storage areas are de-allocated, and returned to the pool of available storage.
Tracing garbage collectors can cause significant interruptions of program execution. One approach to limiting the length of interruption is to define a "threatened set" of objects subject to collection. This approach is referred to as "partially threatening." By limiting the threatened set, the amount of tracing can be reduced, improving performance. For example, in "generational" garbage collectors, only younger objects are threatened. However, it is still necessary to determine whether an object pointed to is in the threatened set, preferably without following each pointer. One solution is to store newer objects in a particular region of memory as they are created. The garbage collector then need only scan for pointers to address in this region. Such generational collectors copy the threatened but reachable objects into the "non-threatened" memory space reserved for older objects, leaving a free, threatened space for the next generation.
Although copying collectors have the advantage of compacting the use of memory space, the copying operation is time-consuming. Further, it is not possible to sub-divide the threatened set at the time of collection. Still further, copying collectors must have knowledge of which bits in an object are address pointers (as opposed to data or instructions), because they update the pointers when they move objects to the non-threatened region. Copying collectors are thus incompatible with "conservative" garbage collection. In conservative collectors, the collector does not have perfect knowledge about the location of pointers, but makes conservative assumptions about which patterns of bits might be pointers to allocated objects and treats the object "pointed to" as reachable.